partiels/091215/.svn/text-base/partiel_Mathsdis_S1_Decembre 09.tex.svn-base

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage{dsfont}
  10 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  11 \usepackage[dvips]{graphics}
  12 \usepackage{epsfig}
  13 \usepackage{calc}
  14 \usepackage{tabls}
  15 \usepackage{slashbox}
  16 \usepackage{times}
  17 \usepackage{tabularx}
  18 \usepackage{multicol}
  19 \usepackage{textcomp}
  20
  21 \usepackage{pst-all}
  22
  23 \usepackage[a4paper]{geometry}
  24
  25 \input{symboles.sty}
  26
  27 \geometry{hmargin=1cm, vmargin=1.5cm}
  28
  29 \title{
  30 Département d'informatique (décembre 09).\\
  31 Partiel de mathématiques discrètes. Semestre 1}
  32
  33 \date{}
  34
  35 \begin{document}
  36
  37 \vspace{-5em}
  38 \maketitle
  39
  40
  41 \vspace{-5em}
  42 \noindent Seule une fiche manuscrite de format A5 est autorisée.\\
  43
  44
  45
  46
  47 \vspace{-3em}
  48 \section{QCM}
  49
  50 Cette partie contient 60 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).
  51
  52 Q. 1. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?
  53
  54 %Q. 2. La puissance du continu est la puissance de $\mathds{R}$.
  55 %L'assertion proposée est vraie ou fausse ?
  56
  57 %Q. 80.
  58 Q. 2. Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$.
  59 Si $t_1 +  t_2 = 1$ alors $t_1 = 1 $ et $t_2$ a une valeur quelconque, et vice versa.
  60  L'assertion proposée est vraie ou fausse ?
  61
  62
  63
  64
  65 Q. 3. Soit $\mathcal{R}$ une relation binaire. Pour tout $x$ de $E$, il existe au plus un $y$ de $F$ tel que $x \mathcal{R} y$.
  66 L'assertion proposée est vraie ou fausse ?
  67
  68 Q. 4. Une application est une relation fonctionnelle telle que tout élément de l'ensemble de départ possède au moins une image.
  69 L'assertion proposée est vraie ou fausse ?
  70
  71 Q. 5. Une application est une relation binaire. L'assertion proposée est vraie ou fausse ?
  72
  73 Q. 6. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
  74 dans le diagramme cartésien:
  75 \begin{multicols}{2}
  76 \begin{center}
  77 \psset{xunit=0.5, yunit=0.5}
  78 \begin{pspicture}(0,-0.5)(6,6)
  79 %\psgrid
  80 \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
  81 \savedata{\mydata}[
  82 {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
  83 \listplot[plotstyle=dots,showpoints=true]{\mydata}
  84 \end{pspicture}
  85 \end{center}
  86
  87 Le domaine de $\mathcal{R}$ est-il $\{1,2,3,4,5\}$?
  88 \end{multicols}
  89
  90 Q. 7. $\sqrt{} : \mathbb{R}^+ \longrightarrow \mathbb{R}$ est surjective.
  91 L'assertion proposée est vraie ou fausse ?
  92
  93 Q. 8. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?
  94
  95 Q. 9. Les relations d'ordre sont les relations réflexive, symétrique et transitive. L'assertion proposée est vraie ou fausse ?
  96
  97 Q. 10. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite  réflexive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ?
  98
  99 Q. 11. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par
 100 $R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$.
 101 A-t-on $R^{-1}=\{(1,3),(1,4),(3,2),(3,3),(3,4),(1,3),(1,4),(3,2),(3,3),(3,4),\}$?
 102
 103
 104 Q. 12. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
 105 dans le diagramme cartésien:
 106 \begin{multicols}{2}
 107 \begin{center}
 108 \psset{xunit=0.5, yunit=0.5}
 109 \begin{pspicture}(0,-0.5)(6,6)
 110 %\psgrid
 111 \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
 112 \savedata{\mydata}[
 113 {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
 114 \listplot[plotstyle=dots,showpoints=true]{\mydata}
 115 \end{pspicture}
 116 \end{center}
 117
 118 Le domaine de $\mathcal{R}$ est-il $\{1,3,5\}$?
 119 \end{multicols}
 120
 121 Q. 13. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$.
 122 L'assertion proposée est vraie ou fausse ?
 123
 124 %doublon
 125 %Q. 14. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?
 126 % Q.70.
 127 Q. 14. Une application bijective est surjective. L'assertion proposée est vraie ou fausse ?
 128
 129
 130
 131
 132 Q. 15. $|$ est une relation d'ordre dans $\mathds{Z}$.
 133 L'assertion proposée est vraie ou fausse ?
 134
 135 Q. 16. $(\mathds{R},\leqslant)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?
 136
 137 Q. 17. Les relations d'ordre sont les relations symétrique, antisymétrique et transitive.
 138 L'assertion proposée est vraie ou fausse ?
 139
 140 % doublon
 141 %Q. 18. Une application est une relation binaire.
 142 %L'assertion proposée est vraie ou fausse ?
 143 % Q. 64.
 144 Q. 18. $\sin : [0,\pi] \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ?
 145
 146
 147
 148 Q. 19. $(\mathds{N},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?
 149
 150 Q. 20. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective. L'assertion proposée est vraie ou fausse ?
 151
 152 Q. 21. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$ est une relation fonctionnelle.
 153 L'assertion proposée est vraie ou fausse ?
 154
 155 Q. 22. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $\forall x \in E, (x,x) \in G$. L'assertion proposée est vraie ou fausse ?
 156
 157 Q. 23.
 158 Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression
 159 $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est $\overline{a}bcde$.
 160  L'assertion proposée est vraie ou fausse ?
 161
 162
 163 Q. 24. $(\mathds{N}^*,|)$ est un ensemble ordonné.
 164 L'assertion proposée est vraie ou fausse ?
 165
 166 Q. 25. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
 167 dans le diagramme cartésien:
 168 \begin{multicols}{2}
 169 \begin{center}
 170 \psset{xunit=0.5, yunit=0.5}
 171 \begin{pspicture}(0,-0.5)(6,6)
 172 %\psgrid
 173 \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
 174 \savedata{\mydata}[
 175 {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
 176 \listplot[plotstyle=dots,showpoints=true]{\mydata}
 177 \end{pspicture}
 178 \end{center}
 179
 180 On propose les affirmations suivantes:
 181 \begin{enumerate}
 182 \item \label{item:af1} $1 \mathcal{R}4$;
 183 \item \label{item:af2} $2 \mathcal{R}5$;
 184 \item \label{item:af3} $3 \mathcal{R}1$;
 185 \item \label{item:af4} $5 \mathcal{R}3$.
 186 \end{enumerate}
 187  Toutes les relations sont-elles vraies?
 188
 189 \end{multicols}
 190 Q. 26.
 191 Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression
 192 $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1.
 193  L'assertion proposée est vraie ou fausse ?
 194
 195
 196 Q. 27. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
 197 dans le diagramme cartésien:
 198 \begin{multicols}{2}
 199 \begin{center}
 200 \psset{xunit=0.5, yunit=0.5}
 201 \begin{pspicture}(0,-0.5)(6,6)
 202 %\psgrid
 203 \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
 204 \savedata{\mydata}[
 205 {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
 206 \listplot[plotstyle=dots,showpoints=true]{\mydata}
 207 \end{pspicture}
 208 \end{center}
 209
 210 On propose les affirmations suivantes:
 211 \begin{enumerate}
 212 \item \label{item:af1b} $1 \mathcal{R}4$;
 213 \item \label{item:af2b} $2 \mathcal{R}5$;
 214 \item \label{item:af3b} $3 \mathcal{R}1$;
 215 \item \label{item:af4b} $5 \mathcal{R}3$.
 216 \end{enumerate}
 217 L'item \ref{item:af4b} est-il toujours faux?
 218
 219 \end{multicols}
 220
 221 Q. 28. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs. L'assertion proposée est vraie ou fausse ?
 222
 223 Q. 29. Une application de $E$ dans $F$ est telle que $\forall x \in E$, il existe un unique élément $y \in F$ en relation avec $x$. L'assertion proposée est vraie ou fausse ?
 224
 225 Q. 30. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?
 226
 227 Q. 31. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$ est une relation binaire.
 228 L'assertion proposée est vraie ou fausse ?
 229
 230 %Q. 32. $\mathds{C}$ a la puissance du continu.
 231 %L'assertion proposée est vraie ou fausse ?\\
 232 % Q. 79.
 233 % doublon
 234 %Q. 32. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective.
 235 %L'assertion proposée est vraie ou fausse ?
 236 Q. 32. Les applications bijectives sont les applications injectives et surjectives. L'assertion proposée est vraie ou fausse ?
 237
 238
 239 Q. 33. Soit $\mathcal{R}$ une relation binaire. Le graphe de $\mathcal{R}$ est symétrique par rapport à la diagonale.
 240 L'assertion proposée est vraie ou fausse ?
 241
 242 %Q. 34. La puissance du continu est la puissance de $\mathds{N}$.
 243 %L'assertion proposée est vraie ou fausse ?
 244
 245 %Q. 78.
 246 Q. 34. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ?
 247
 248
 249 % doublon
 250 %Q. 35. Les relations d'ordre sont les relations réflexive, symétrique et transitive.
 251 %L'assertion proposée est vraie ou fausse ?
 252 Q. 35.
 253 $\subset$ est une relation d'ordre dans $\mathcal{P}(E)$.
 254  L'assertion proposée est vraie ou fausse ?
 255
 256
 257
 258 Q. 36. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède au plus un antécédent. L'assertion proposée est vraie ou fausse ?
 259
 260 Q. 37. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ?
 261
 262 Q. 38. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ?
 263
 264 Q. 39. Une application surjective est une application telle que tout élément de l'ensemble d'arrivée possède au moins un antécédent.
 265 L'assertion proposée est vraie ou fausse ?
 266
 267 Q. 40. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
 268 dans le diagramme cartésien:
 269 \begin{multicols}{2}
 270 \begin{center}
 271 \psset{xunit=0.5, yunit=0.5}
 272 \begin{pspicture}(0,-0.5)(6,6)
 273 %\psgrid
 274 \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
 275 \savedata{\mydata}[
 276 {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
 277 \listplot[plotstyle=dots,showpoints=true]{\mydata}
 278 \end{pspicture}
 279 \end{center}
 280
 281 Le domaine de $\mathcal{R}$ est-il
 282 $\{1,3,5\} \times \{1,2,4,5\}$?
 283
 284 \end{multicols}
 285 Q. 41. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective.
 286 L'assertion proposée est vraie ou fausse ?
 287
 288 %Q. 42. $\mathds{Z}$ a la puissance du continu.
 289 %L'assertion proposée est vraie ou fausse ?
 290
 291 %Q. 77.
 292 Q. 42. Une application de $F$ dans $E$ est telle que $\forall x \in F$, il existe un unique élément $y \in E$ en relation avec $x$.
 293 L'assertion proposée est vraie ou fausse ?
 294
 295
 296 Q. 43. Toute application injective est surjective.
 297 L'assertion proposée est vraie ou fausse ?
 298
 299 Q. 44. On a défini une relation binaire $\mathcal{R}$ entre deux ensembles $E$ et $F$ lorsqu’on s'est donné une partie de $E \times F$.
 300 L'assertion proposée est vraie ou fausse ?
 301
 302 %Q. 45. $\mathcal{P}\left(\mathds{R}\right)$ a la puissance du continu.
 303 %L'assertion proposée est vraie ou fausse ?\\
 304 %Q. 76.
 305 %doublon
 306 %Q. 45. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?
 307 % doublon
 308 % Q. 45. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ?
 309 Q.45. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$). L'assertion proposée est vraie ou fausse ?
 310
 311
 312 Q. 46. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ?
 313
 314 Q. 47. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?
 315
 316 Q. 48. \og $x \mathcal{R} y$ si et seulement si $x+y$ est pair \fg{} est une relation d'ordre sur l'ensemble des entiers relatifs.
 317 L'assertion proposée est vraie ou fausse ?
 318
 319 Q. 49. $\{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$ est une relation fonctionnelle.
 320 L'assertion proposée est vraie ou fausse ?
 321
 322 %Q. 50. $\mathcal{P}\left(\mathds{N}\right)$ a la puissance du continu.
 323 %L'assertion proposée est vraie ou fausse ?\\
 324 %Q. 75.
 325
 326 Q. 50. $\leqslant$ est une relation d'ordre dans $\mathds{R}$.
 327 L'assertion proposée est vraie ou fausse ?
 328
 329 Q. 51. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $$\forall (x,y,z) \in E^3, (x,y) \in G \textrm{ et } (y,z) \in G \Longrightarrow (x,z) \in G$$. L'assertion proposée est vraie ou fausse ?
 330
 331 %Q. 52. $\mathds{D}$ a la puissance du continu.
 332 %L'assertion proposée est vraie ou fausse ?\\
 333 %Q. 74.
 334 Q. 52. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par
 335 $R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$.
 336 A-t-on  $R^{-1}=\{(3,1),(4,1),(2,3),(3,3),(4,3)\}$?
 337
 338
 339 Q. 53. $(\mathds{Z},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?
 340
 341 Q. 54.
 342 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 343 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 344 L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ?
 345
 346 Q. 55. $|$ est une relation d'ordre dans $\mathds{N}^*$.
 347 L'assertion proposée est vraie ou fausse ?
 348
 349 Q. 56.
 350 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif,
 351 le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
 352 L'égalité $a+b+c+d=0$ est établie si et seulement si $a= b= c= d = 0$. L'assertion  proposée est vraie ou fausse ?
 353
 354 Q. 57. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $$\forall (x,y,z) \in E^3, x \mathcal{R} y \textrm{ et } y \mathcal{R} z \Longrightarrow x \mathcal{R} z$$. L'assertion proposée est vraie ou fausse ?
 355
 356 Q. 58.
 357 Étant données les fonctions $f:A \rightarrow B$,
 358 $g:B \rightarrow C$ et
 359 $h:C \rightarrow D$ définies par le diagramme suivants
 360 \begin{multicols}{2}
 361 \begin{center}
 362 \pspicture*(-1,-1)(7,5.4)
 363 \scalebox{1}{
 364 \cnodeput*(0,4){a}{a}
 365 \cnodeput*(0,3){b}{b}
 366 \cnodeput*(0,2){c}{c}
 367 \cnodeput*(2,4){1}{1}
 368 \cnodeput*(2,3){2}{2}
 369 \cnodeput*(2,2){3}{3}
 370 \cnodeput*(4,4){x}{x}
 371 \cnodeput*(4,3){y}{y}
 372 \cnodeput*(4,2){z}{z}
 373 \cnodeput*(4,1){w}{w}
 374 \cnodeput*(6,4){4}{4}
 375 \cnodeput*(6,3){5}{5}
 376 \cnodeput*(6,2){6}{6}
 377
 378 \rput(-0.2,5.2){$A$}
 379 \rput(1.8,5.2){$B$}
 380 \rput(3.8,5.2){$C$}
 381 \rput(5.8,5.2){$D$}
 382
 383 \rput(1,0.5){$f$}
 384 \rput(3,0.5){$g$}
 385 \rput(5,0.5){$h$}
 386
 387
 388 \psellipse(0,3)(0.5,2)
 389 \psellipse(2,3)(0.5,2)
 390 \psellipse(4,2.5)(0.5,2.5)
 391 \psellipse(6,3)(0.5,2)
 392
 393 \ncline{->}{a}{2}
 394 \ncline{->}{b}{1}
 395 \ncline{->}{c}{2}
 396 \ncline{->}{2}{x}
 397 \ncline{->}{1}{y}
 398 \ncline{->}{3}{w}
 399 \ncline{->}{x}{4}
 400 \ncline{->}{z}{4}
 401 \ncline{->}{y}{6}
 402 \ncline{->}{w}{5}
 403    }
 404  \endpspicture
 405 \end{center}
 406
 407 $f$ est-elle ni injective ni surjective?
 408
 409 \end{multicols}
 410
 411 %doublon
 412 %Q. 59. $(\mathds{N},|)$ est un ensemble ordonné.
 413 %L'assertion proposée est vraie ou fausse ?
 414 Q.59. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $E$ possède exactement une image dans $F$.
 415 L'assertion proposée est vraie ou fausse ?
 416
 417 %doublon
 418 %Q. 60. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs.
 419 %L'assertion proposée est vraie ou fausse ?
 420
 421 Q. 60. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède exactement un antécédent.
 422  L'assertion proposée est vraie ou fausse ?
 423
 424 % Q. 62.
 425
 426 % Q. 63.
 427
 428 % Q. 65.
 429 % Etant données les fonctions $f:A \rightarrow B$,
 430 % $g:B \rightarrow C$ et
 431 % $h:C \rightarrow D$ définies par le diagramme suivants
 432
 433 % \begin{center}
 434 % \pspicture*(-1,-1)(7,5.4)
 435 % \scalebox{1}{
 436 % \cnodeput*(0,4){a}{a}
 437 % \cnodeput*(0,3){b}{b}
 438 % \cnodeput*(0,2){c}{c}
 439 % \cnodeput*(2,4){1}{1}
 440 % \cnodeput*(2,3){2}{2}
 441 % \cnodeput*(2,2){3}{3}
 442 % \cnodeput*(4,4){x}{x}
 443 % \cnodeput*(4,3){y}{y}
 444 % \cnodeput*(4,2){z}{z}
 445 % \cnodeput*(4,1){w}{w}
 446 % \cnodeput*(6,4){4}{4}
 447 % \cnodeput*(6,3){5}{5}
 448 % \cnodeput*(6,2){6}{6}
 449
 450 % \rput(-0.2,5.2){$A$}
 451 % \rput(1.8,5.2){$B$}
 452 % \rput(3.8,5.2){$C$}
 453 % \rput(5.8,5.2){$D$}
 454
 455 % \rput(1,0.5){$f$}
 456 % \rput(3,0.5){$g$}
 457 % \rput(5,0.5){$h$}
 458
 459
 460 % \psellipse(0,3)(0.5,2)
 461 % \psellipse(2,3)(0.5,2)
 462 % \psellipse(4,2.5)(0.5,2.5)
 463 % \psellipse(6,3)(0.5,2)
 464
 465 % \ncline{->}{a}{2}
 466 % \ncline{->}{b}{1}
 467 % \ncline{->}{c}{2}
 468 % \ncline{->}{2}{x}
 469 % \ncline{->}{1}{y}
 470 % \ncline{->}{3}{w}
 471 % \ncline{->}{x}{4}
 472 % \ncline{->}{z}{4}
 473 % \ncline{->}{y}{6}
 474 % \ncline{->}{w}{5}
 475 %    }
 476 %  \endpspicture
 477 % \end{center}
 478
 479 % $h \circ g$ est-elle surjective?
 480
 481 % Q. 66. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $F$ possède exactement un antécédant dans $E$. L'assertion proposée est vraie ou fausse ?
 482
 483 % Q. 67. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ?
 484
 485 % Q. 68. Soit $\mathcal{R}$ une relation binaire. Il est possible d'avoir $x \mathcal{R} y$ sans avoir $y \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?
 486
 487 % Q. 69.
 488 %
 489 %
 490 % %Q. 72. $\mathds{Q}$ a la puissance du continu.
 491 % %L'assertion proposée est vraie ou fausse ?\\
 492 % Q. 72.
 493
 494
 495 \begin{large}
 496 \begin{center}
 497 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 498 \hline
 499 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 500 \hline
 501 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 502 \hline
 503 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 504 \hline
 505 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 506 \hline
 507 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 508 \hline
 509 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 510 \hline
 511 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 512 \hline
 513 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 514 \hline
 515 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 516 \hline
 517 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 518 \hline
 519 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 520 \hline
 521 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
 522 \hline
 523 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
 524 \hline
 525 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
 526 \hline
 527 Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\
 528 \hline
 529 Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\
 530 \hline
 531 Q. 46 & &  & Q. 47 & &  & Q. 48 & &  \\
 532 \hline
 533 Q. 49 & &  & Q. 50 & &  & Q. 51 & &  \\
 534 \hline
 535 Q. 52 & &  & Q. 53 & &  & Q. 54 & &  \\
 536 \hline
 537 Q. 55 & &  & Q. 56 & &  & Q. 57 & &  \\
 538 \hline
 539 Q. 58 & &  & Q. 59 & &  & Q. 60 & &  \\
 540 \hline
 541 \end{tabular}
 542 \end{center}
 543 \end{large}
 544
 545 \newpage
 546 \section{Problèmes}
 547
 548 Vous traiterez au choix deux des trois problèmes suivants.
 549
 550 \subsection{Une relation d'ordre en algèbre de Boole}
 551 Dans une algèbre de Boole munie des opérateurs classiques +, .
 552 et $\overline{\begin{array}{l}~\end{array}}$
 553 soit la relation $R$ définie par
 554 $$ x R y \Leftrightarrow x +y = y $$
 555
 556 \begin{enumerate}
 557 \item A-t-on
 558   $a\overline{c}d ~R~ ad$,
 559   $ad ~R~ a\overline{c}d$,
 560   $a\overline{c}d ~R~ \overline{a}\overline{b}cd$ ? Justifier à chaque fois.
 561 \item Montrer que $R$ est une relation d'ordre
 562   (réflexive, antisymétrique et transitive).
 563 \item La relation est-elle totale? Partielle? Justifier.
 564 \end{enumerate}
 565
 566 \subsection{Résolution d'équations en  algèbre de Boole}
 567
 568 On considère une boite noire qui réalise l'addition de deux bits
 569 $a$ et $b$ plus une retenu entrante $c_{\textit{in}}$.
 570 Elle produit un résultat $s$ et un bit de retenu $c_{\textit{out}}$ en
 571 se conformant au tableau suivant:
 572 $$
 573  \begin{array}{|c|c|c|c|c|}
 574    \hline
 575    a &b & c_{\textit{in}} & c_{\textit{out}} & s \\
 576    \hline
 577    0 &0 & 0 &0 & 0 \\
 578    \hline
 579    0 &0 & 1 &0 & 1 \\
 580    \hline
 581    0 &1 & 0 &0 & 1 \\
 582    \hline
 583    0 &1 & 1 &1 & 0 \\
 584    \hline
 585    1 &0 & 0 &0 & 1 \\
 586    \hline
 587    1 &0 & 1 &1 & 0 \\
 588    \hline
 589    1 &1 & 0 &1 & 0 \\
 590    \hline
 591    1 &1 & 0 &1 & 1 \\
 592    \hline
 593  \end{array}
 594 $$
 595 \begin{enumerate}
 596 \item Montrer que la sortie $s$ est
 597   $c_{\textit{in}}(\overline{a}.\overline{b} + a.b) +
 598   \overline{c_{\textit{in}}}(\overline{a}.b + a.\overline{b})$
 599 \item Montrer que la retenue $c_{\textit{out}}$ de sortie est
 600   $a.b + c_{\textit{in}}.a + c_{\textit{in}}.b$
 601 \item Résoudre algébriquement l'équation $s = c_{\textit{out}}$ dont les
 602   variables sont $c_{\textit{in}}$, $a$ et $b$.
 603   Vérifier la correction des réponses à l'aide du tableau donné ci-dessus.
 604 \end{enumerate}
 605
 606 \subsection{Les infinis}
 607 \begin{enumerate}
 608 \item Parmi les ensembles suivants, $\mathbb{N}, \mathbb{Z}, \mathbb{D}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$, lesquels sont
 609 dénombrables? Justifier.
 610
 611
 612 \item L'ensemble des nombres transcendants est-il dénombrable? Justifier.
 613
 614 \item Quelle est la définition d'un ensemble infini?
 615
 616 \item Combien y a-t-il d'infinis? Justifier.
 617
 618 \item Démontrez que l'intervalle réel [0,1] n'est pas dénombrable.
 619 \end{enumerate}
 620
 621 \end{document}